package com.lihepeng.leecode.linkedList;

import java.util.PriorityQueue;

/**
 *给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length==0) {
            return null;
        }
        ListNode dumpy = new ListNode(-1);
        ListNode p = dumpy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.value -b.value));
        for (ListNode head:lists){
            if (head!=null) {
                pq.add(head);
            }
        }
        while (!pq.isEmpty()) {
            ListNode poll = pq.poll();
            p.next = poll;
            if (poll.next != null) {
                pq.add(poll.next);
            }
            p = p.next;
        }
        return dumpy.next;
    }
}
